package pl.edu.agh.gronoMining.frequentSubgraphFinder.frequentSearcher.subgraph.impl;

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;

import org.apache.log4j.Logger;

import pl.edu.agh.gronoMining.frequentSubgraphFinder.frequentSearcher.subgraph.DFSCode;
import pl.edu.agh.gronoMining.frequentSubgraphFinder.frequentSearcher.subgraph.SubgraphMove;
import pl.edu.agh.gronoMining.frequentSubgraphFinder.graph.Edge;
import pl.edu.agh.gronoMining.frequentSubgraphFinder.graph.Node;
import pl.edu.agh.gronoMining.frequentSubgraphFinder.strategy.Strategy;

public class StartNodeInstance {
	
	private static final int NODE_CHECKED = 0;
	private static final int NODE_NOT_CHECKED = 1;
	
		/** id of this instance */
	private int id = -1;
	
		/** nodes of graph from this instance (as map id->node)*/
	private Map<Integer, Node> nodes;
	
		/** set of edges of graph from this instance */
	private Set<Edge> edges;
	
		/** map that converts outer to inner node id's */
	private Map<Node, Integer> outerToInnerNodeIdMap = new HashMap<Node, Integer>();
	
		/** inner nodes index, used when adding new node to this instance subgraph */
	int nodesIndex;
	
	int additionalNodesIndex = -1;
	
		/** current node that is an end of path */
	private Node pathNode;
	
		/** true if current subgraph is path */
	private boolean isPath;
	
		/** reference to strategy object */
	private Strategy strategy;
	
		/** reference to edge markers*/
	private Map<Edge, EdgeMarker> edgeMarkers;
	
	private Map<Node, Integer> nodeMarkers;
	
		/** map that is used while generating moves. It contains reference (node1Id -> node2Id) -> counter.
		 * Used when strategy rule for (node1Id -> node2Id) is >0 */
	private Map<Integer, Map<Integer, Integer>> strategyCounters = new HashMap<Integer, Map<Integer, Integer>>();
	
		/** temporary set of new instances, when some new instances was created while move */
	private Set<StartNodeInstance> newInstances;
	
		/** reference to last added edge */
	private Edge lastAddedEdge = null;
	
	private static Logger logger = Logger.getLogger(StartNodeInstance.class);

		/**
		 * @param beginNodes set of nodes of subgraph of this instance
		 * @param beginEdges set of edges of subgraph of this instance
		 * @param pathNode path node of this subgraph
		 * @param index inner node index begin value
		 * @param strategy reference to strategy object
		 * @param edgeMarkers reference to edge markers
		 */
	public StartNodeInstance(Map<Integer,Node> beginNodes,	Set<Edge> beginEdges, int index, Strategy strategy, Map<Edge, EdgeMarker> edgeMarkers) {
		this.nodes = beginNodes;
		this.edges = beginEdges;
		this.nodesIndex = index;
		this.strategy = strategy;
		this.edgeMarkers = edgeMarkers;
		this.nodeMarkers = new HashMap<Node, Integer>();
			// generate outerToInnerNodeIdMap
		for (int nodeId : this.nodes.keySet())
			this.outerToInnerNodeIdMap.put(this.nodes.get(nodeId), nodeId);
	}
	
	public void setId(int id) {
		this.id = id;
	}
	
	public int getId() {
		return id;
	}
	
	/**
	 * generates list of possible moves of this instance subgraph
	 */
	public List<SubgraphMove> getPossibleMoves(DFSCode dfs, Set<DFSCode> resultDfsSet) {
		List<SubgraphMove> resultSet = new LinkedList<SubgraphMove>();		
		
			// We need to make copy because we will modify original keySet while isPossibleNewMove method
		Set<Integer> nodesKeySetCopy = new HashSet<Integer>();
		for (int nodeId : this.nodes.keySet()) {
			nodesKeySetCopy.add(nodeId);
		}
			// for all nodes...
		for (int nodeId : nodesKeySetCopy) {
			
			Node node = this.nodes.get(nodeId);
			
			Integer nodeMarker = this.nodeMarkers.get(node);
			if (nodeMarker != null) {
				//if (nodeMarker == NODE_CHECKED)
				//	continue;
			}
			
			//logger.info("generating moves from node "+node);
			
			//logger.info(this.nodes.keySet().toString());
			
			boolean isCreatingPath = false;
			if (node.equals(this.pathNode) && this.isPath)
				isCreatingPath = true;
			
			int isNodeChecked = NODE_CHECKED;
			
				// for all edges...
			for (Edge e : node.getEdges()) {
				//logger.info("check edge "+e);
				
				if (this.edges.contains(e))
					continue;
				
				Node toNode = e.getOtherNode(node);
				
				// check strategy
				Integer str = strategy.getStrategyFor(node.getType(), toNode.getType());
				if (str != null) {
					if (str < 0)
						continue;
					if (str > 0) {
						Map<Integer, Integer> mapForThisType = this.strategyCounters.get(node.getType());
						if (mapForThisType != null) {
							Integer counter = mapForThisType.get(toNode.getType());
							if (counter != null) {
								if (counter == 0) {
									isNodeChecked = NODE_NOT_CHECKED;
									continue;
								}
							}
						}							
					}
				}
				
					// check markers
				EdgeMarker marker = this.edgeMarkers.get(e);
				if (marker != null) {
					if (marker.isAbsoluteMarked()) {
						if (marker.isAbsoluteFrequent()) {
							
							boolean result = this.isEdgeCheckedAsFrequent(node, e);
							if (result == true) {
								this.edges.add(e);
								this.addAllFrequentNodes(e.getOtherNode(node));
								resultDfsSet.add(this.getAsDfs());
								continue;
							}
							
						} else {
							continue;
						}
					} else {
						Boolean isFrequent = marker.getMarkerForDfs(dfs);
						isNodeChecked = NODE_NOT_CHECKED;
						if (isFrequent != null) {
							if (isFrequent) {
								
							} else {
								//logger.info("dfs was previously - skiping");
								continue;
							}
						}
					}
				}
			
				isNodeChecked = NODE_NOT_CHECKED;
				
				SubgraphMove move = this.createMove(nodeId, e, isCreatingPath);
				
				resultSet.add(move);
				//logger.info("ok - "+move);
			}
			
			if (isNodeChecked == NODE_CHECKED)
				this.nodeMarkers.put(node, NODE_CHECKED);
		}
		
		// mozna posortowac resultSet
		
		return resultSet;
	}
	
	/**
	 * Perform move in this instance
	 * @param move move to perform
	 * @param isActive true if this instance is active instance
	 * @return 0 - move impossible, >0 inner index of new node, <0 - -inner index
	 * 		of new node and new instances was created
	 */
	public int performMove(SubgraphMove move, boolean isActive) {
		int type = move.getType();
		int fromNodeId = move.getFromNodeId();
		Node fromNode = this.nodes.get(fromNodeId);
		//logger.info("check moves from node "+fromNode);
		
		if (type == SubgraphMove.ADD_EDGE) {
			
			int nextNodeId = move.getToNode();
			Node nextNode = this.nodes.get(nextNodeId);
			//logger.info("adding edge");
			//logger.info("from: "+fromNode);
			//logger.info("to: "+nextNode);
			Edge e = fromNode.getEdgeToNode(nextNode);
			//logger.info(e);
			if (e != null) {
				this.edges.add(e);
				this.lastAddedEdge = e;
				return this.nodesIndex;
			} else {
				return 0;
			}
			
		} else if (type == SubgraphMove.ADD_NODE_AND_EDGE) {
		
			List<Edge> possibleEdges = new LinkedList<Edge>();
			int toNodeLabel = move.getToNode();
			int toNodeType = move.getAdditionalArg();
			
				// if it is active instance
			if (isActive) {
				Node toNode = move.getOrgToNode();
				
				//logger.info("move to " + toNode);
				
				possibleEdges.add(fromNode.getEdgeToNode(toNode));
					// if strategy rule for this pair of nodes is >0, check if counter exist.
					// If exist increment it, if not crate one and set start value
				Integer str = this.strategy.getStrategyFor(fromNode.getType(), toNode.getType());
				if (str != null) {
					if (str > 0) {
						Map<Integer, Integer> mapForThisType = this.strategyCounters.get(fromNode.getType());
						if (mapForThisType == null) {
							mapForThisType = new HashMap<Integer, Integer>();
							this.strategyCounters.put(fromNode.getType(), mapForThisType);
						}
						Integer counter = mapForThisType.get(toNode.getType());
						if (counter == null) {
							counter = new Integer(str);
							mapForThisType.put(toNode.getType(), counter);
						}
						mapForThisType.put(toNode.getType(), counter-1);
					}
				}
				
				// if it's not active instance
			} else {
					// put to possibleEdges set all nodes that connect node of this subgraph with node with
					// name and type same as in move
				try {
				for (Edge e : fromNode.getEdges()) {
					//logger.debug("check edge "+e);
					if (! this.edges.contains(e)) {
						Node toNode = e.getOtherNode(fromNode);
						if (toNode.getLabel() == toNodeLabel && toNode.getType() == toNodeType) {
							possibleEdges.add(e);
						}
					}
				}
				}catch (Exception e) {
					logger.info(fromNodeId);
					e.printStackTrace();
					System.exit(0);
				}
			}
			
				// if no edges found, move is impossible
			if (possibleEdges.size() == 0) {
				return 0;
				
			} else {
					// reset set of possible new instances
				this.newInstances = new HashSet<StartNodeInstance>();
				Node currentPathNode = this.pathNode;
				boolean currentIsPath = this.isPath;
				int counter = 1;	// this counter counts possible edges from possibleEdges set
				for (Edge e : possibleEdges) {
						
					// 	perform changes in this instance
					//logger.info("use edge "+e);
					Node nextNode = e.getOtherNode(fromNode);
					this.nodes.put(this.nodesIndex, nextNode);
					this.outerToInnerNodeIdMap.put(nextNode, this.nodesIndex);
					//logger.info("put - "+this.nodesIndex);
					this.edges.add(e);
					if (fromNode.equals(this.pathNode))
						this.pathNode = nextNode;
					this.isPath = move.isCreatingPath();
					this.lastAddedEdge = e;
					this.nodesIndex++;
						// if its not last of edges from possibleEdges, create copy of current instance and revert changes
					if (counter < possibleEdges.size()) {
						//logger.info("---create new instance---");
						this.newInstances.add(this.makeCopy());
						this.nodes.remove(this.nodesIndex);
						this.outerToInnerNodeIdMap.remove(nextNode);
						this.edges.remove(e);
						this.pathNode = currentPathNode;
						this.isPath = currentIsPath;
						this.nodesIndex--;
					}
					
					counter++;
				}
				
				if (newInstances.size() == 0)
					return this.nodesIndex - 1;
				else
					return - (this.nodesIndex - 1);		
			}
		}		
		return 0;
	}
	
	/**
	 * undo move
	 * @param move move to undo
	 * @param newNodeId id of node that was added in this move
	 * @param isActive true if instance is active
	 */
	public void undoMove(SubgraphMove move, int newNodeId, boolean isActive) {
		
		if (move.getType() == SubgraphMove.ADD_EDGE) {
			
			Node node1 = this.nodes.get(move.getFromNodeId());
			Node node2 = this.nodes.get(move.getToNode());
			Edge e = node1.getEdgeToNode(node2);
			this.edges.remove(e);
			
		} else if (move.getType() == SubgraphMove.ADD_NODE_AND_EDGE) {
			
			//logger.info("undo "+move);
			
			Node node1 = this.nodes.get(move.getFromNodeId());
			// logger.info("node 1: " + node1);
			// logger.info("to node inner id = " + newNodeId);
			Node node2 = this.nodes.get(newNodeId);
			//logger.info("node 2: " + node2);
			
			Edge e = node1.getEdgeToNode(node2);
			
			this.edges.remove(e);
			
				// if strategyCounter for this pair of nodes exist, decrement it
			if (isActive) {
				//logger.info("remove edge "+e);
				Integer str = this.strategy.getStrategyFor(node1.getType(), node2.getType());
				if (str != null) {
					if (str > 0) {
						Map<Integer, Integer> mapForThisType = this.strategyCounters.get(node1.getType());
						Integer counter = mapForThisType.get(node2.getType());
						mapForThisType.put(node2.getType(), counter+1);
					}
				}
				// usun wszystkie czeste z danego wierzcholka
				this.removeAllFrequentNodes(node2);
			}
			
			this.nodes.remove(newNodeId);
			if (this.pathNode.equals(node2))
				this.pathNode = node1;
			this.isPath = move.wasPath();
			this.nodesIndex--;
			
				// if strategyCounter for this pair of nodes exist, decrement it
		}
	}
	
	public Set<StartNodeInstance> getNewInstances() {
		return this.newInstances;
	}
	
		/**
		 * @return dfs representation of subgraph of this instance
		 */
	public DFSCode getAsDfs() {
		DFSCode dfs = new DFSCodeImpl(this.edges.size());
			// array of all edges of this subgraph
		Edge[] edgeArray = new Edge[this.edges.size()];
		
			// sort nodes in each edge and put it to edgeArray
		int i = 0;
		for (Edge e : this.edges) {
			e.sortNodes(new NodesDFSComparator<Node>());
			edgeArray[i++] = e;
		}
			
			// sort edges using dfs comparator
		Arrays.sort(edgeArray, new EdgeDFSComparator<Edge>(new NodesDFSComparator<Node>()));
		
			// add all edges from array to dfs 
		dfs.createOuterToInnterMap();
		for (i = 0; i<edgeArray.length; i++)
			dfs.addEdge(edgeArray[i]);		
		dfs.removeOuterToInnterMap();

		return dfs;
	}
	
	public Edge getLastAddedEdge() {
		return this.lastAddedEdge;
	}
	
	public void setLastAddedEgge(Edge lastAddedEdge) {
		this.lastAddedEdge = lastAddedEdge;
	}
	
	public void setPathNode(Node node) {
		this.pathNode = node;
	}
	
	public void setIsPath(boolean isPath) {
		this.isPath = isPath;
	}
	
	public boolean equals(Object o) {
		StartNodeInstance instance = (StartNodeInstance) o;
		if (instance.getId() == id)
			return true;
		return false;
	}
	
	public int hashCode() {
		return new Integer(id).hashCode();
	}
	
	/**
	 * make copy of this instance. Make new 'nodes' map and 'edges' set. 
	 * @return new copy of this instance
	 */
	private StartNodeInstance makeCopy() {
		Map<Integer, Node> newNodes = new HashMap<Integer, Node>();	
		for (Integer i : this.nodes.keySet())
			newNodes.put(i, this.nodes.get(i));
		Set<Edge> newEdges = new HashSet<Edge>();
		for (Edge e : this.edges)
			newEdges.add(e);
		StartNodeInstance instance =  new StartNodeInstance(newNodes, newEdges, this.nodesIndex, this.strategy, this.edgeMarkers);
		instance.setLastAddedEgge(this.lastAddedEdge);
		instance.setPathNode(this.pathNode);
		instance.setIsPath(this.isPath);
		return instance;
	}
	
	/**
	 * Create new SubgraphMove
	 * @param fromNodeId inner id first node for move
	 * @param edge move edge
	 * @param isCreatingPath true if move is creating path
	 * @return new SubgraphMove
	 */
	private SubgraphMove createMove(int fromNodeId, Edge edge, boolean isCreatingPath) {
		Node fromNode = this.nodes.get(fromNodeId);
		//logger.info(fromNode);
		SubgraphMove move = null;
		if (this.nodes.containsValue((edge.getOtherNode(fromNode)))) {
			logger.info(" ----------- NIE");
			logger.info(" ----------- "+edge);
			logger.info(" ----------- "+fromNodeId);
			logger.info(" ----------- "+fromNode);
			logger.info(" ----------- "+edge.getOtherNode(fromNode));
			logger.info(" ----------- "+this.outerToInnerNodeIdMap.get(edge.getOtherNode(fromNode)));
			move = new SubgraphMoveImpl(SubgraphMove.ADD_EDGE,
					fromNodeId,  this.outerToInnerNodeIdMap.get(edge.getOtherNode(fromNode)),0 , isCreatingPath, this.isPath);
		} else {
			move = new SubgraphMoveImpl(SubgraphMove.ADD_NODE_AND_EDGE,
					fromNodeId, edge.getOtherNode(fromNode).getLabel(), edge.getOtherNode(fromNode).getType(), isCreatingPath, this.isPath);
			move.setOrgToNode(edge.getOtherNode(fromNode));
		}
		return move;
	}
	
	
	private boolean isEdgeCheckedAsFrequent(Node fromNode, Edge edge) {
		if (this.edges.contains(edge))
			return true;
		Node toNode = edge.getOtherNode(fromNode);
		
		if (this.outerToInnerNodeIdMap.get(toNode) == null)
			return false;
		
		Integer strategy = this.strategy.getStrategyFor(fromNode.getType(), toNode.getType());
		if (strategy != null) {
			if (strategy < 0)
				return true;
			else if (strategy > 0)
				return false;
		}
		
		EdgeMarker marker = this.edgeMarkers.get(edge);
		if (marker == null)
			return false;
		if (! marker.isAbsoluteMarked())
			return false;
		if (! marker.isAbsoluteFrequent())
			return true;
		
		for (Edge e : toNode.getEdges()) {
			if (e.getOtherNode(toNode).equals(fromNode))
				continue;
			boolean result = this.isEdgeCheckedAsFrequent(toNode, e);
			if (result == false)
				return false;
		}
		return true;
	}
	
	private void addAllFrequentNodes(Node n) {
		//logger.info("=== ADDD "+n);
		this.nodes.put(this.additionalNodesIndex, n);
		this.outerToInnerNodeIdMap.put(n, this.additionalNodesIndex);
		this.additionalNodesIndex--;
		this.nodeMarkers.put(n, NODE_CHECKED);
		for (Edge e : n.getEdges()) {
			if (this.edges.contains(e))
				continue;
			Node toNode = e.getOtherNode(n);
			Integer strategy = this.strategy.getStrategyFor(n.getType(), toNode.getType());
			if (strategy != null) {
				if (strategy != 0)
					continue;
			}
			EdgeMarker marker = this.edgeMarkers.get(e);
			if (marker != null) {
				if (! marker.isAbsoluteMarked())
					continue;
				if (! marker.isAbsoluteFrequent())
					continue;
			}
			this.edges.add(e);
			this.nodes.put(this.additionalNodesIndex, toNode);
			this.outerToInnerNodeIdMap.put(toNode, this.additionalNodesIndex);
			this.additionalNodesIndex--;
			//logger.info("=== ADDD new "+toNode);
			this.addAllFrequentNodes(toNode);
		}
	}
	
	private void removeAllFrequentNodes(Node n) {
		//logger.info("=== REMOVE "+n);
		
		int innerId = this.outerToInnerNodeIdMap.get(n);
		//logger.info(innerId);
		this.nodes.remove(innerId);
		this.outerToInnerNodeIdMap.remove(n);
		
		for (Edge e : n.getEdges()) {
			if (this.edges.contains(e)) {
				//logger.info("=== AddRemove "+e);
				Node toNode = e.getOtherNode(n);
				//int innerId = this.outerToInnerNodeIdMap.get(toNode);
				this.edges.remove(e);
				this.removeAllFrequentNodes(toNode);
				//this.nodes.remove(innerId);
				//this.outerToInnerNodeIdMap.remove(toNode);
			}
		}
		
	}
}


